package com.example.algorithm.LRU;

import java.util.HashMap;

/**
 * 纯手写LRU
 * Created by ZMJ on 2020/1/10.
 */
public class MyLRUCache {

    /**
     * lru算法其实就是内存不满的时候淘汰最近最久不使用元素;
     * 为了实现缓存，就必须用一个map来存储数据达到存取数据的时间复杂度为O(1);
     * 然后为了体现最近最久未使用的思想，我们使用双向链表来实现;
     *
     * 主要思想:
     * 每次把当前使用的从链表中删除, 放入到头部, 使用的触发点(set,get).
     * 每次放入内存不够了删除尾巴.
     *
     * 总共有四个函数
     * setHead(Object): 每次都要把当前使用的放在双向链表的头部，有可能是不在链表里面的那么就直接放进头部就好了，如果存在，那就删除链表中的该数据然后在把他放入链表的头部;
     * remove(Object, boolean): 主要是一个辅助的函数，主要是删除传入的节点，boolean这个参数的存在就是为了解决如果缓存满了，那么，我就要去删除tail;
     * get(String): 根据所提供的key返回value;
     * set(String,Object): 这个函数主要是将key和value键值对放入map和链表中;
     */

    // 链表元素
    class LRUNode {
        private String key;
        private Object value;
        private LRUNode pre;
        private LRUNode next;
        public LRUNode() {
        }
        public LRUNode(String key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    // 缓存
    private HashMap<String, LRUNode> map;
    // 头部
    private LRUNode head;
    // 尾巴
    private LRUNode tail;
    // 负载因子, 最大内容容量, 超过就内存淘汰
    private int capacity;

    public MyLRUCache() {
    }
    public MyLRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }


    /**
     * 将最近使用的设置到头上
     * @param node
     */
    public void setHead(LRUNode node) {
        //如果头结点不为空的话，那么就是头插法了
        if (head != null) {
            node.next = head;
            head.pre = node;
        }
        //无论如何，head始终都是当前的节点node
        head = node;
        //如果尾结点为空，那么就把当前节点赋值给尾结点
        if (tail == null) {
            tail = node;
        }
    }

    /**
     * 放入的时候,将其放入导头部,然后遍历链表,如果存在直接删除
     * 然后在判断链表是否超长,超长就把链表尾部多余的删除
     * @param key
     * @param value
     */
    public void set(String key, LRUNode value) {
        //set是最为关键的一步，我们不但要将节点设置到双向链表当中，我们还需要设置到hashmap当中作为缓存来使用
        //就两个维度吧，，一是将这个节点设置为双向链表的头结点，二是放入hashmap当中
        //先设置为头结点
        LRUNode node = map.get(key);
        setHead(node);
        //然后就是放到hashmap里面去了
        //如果不为空，那么，我们就需要更新他的value
        if (node != null) {
            node.value = value ;
            //既然不为空，那么我们就需要更新为头结点的啊
            remove(node, false);
        } else {
            node = new LRUNode(key, value);
            if (map.size() >= capacity) {
                remove(tail, true);
            }
            map.put(key, node);
        }
    }

    /**
     * 每次取出来,在链表中移除,放在头部
     * @param key
     * @return
     */
    public Object get(String key) {
        LRUNode node = map.get(key);
        //如果存在需要干两件事情，先移出该节点，因为他存在所以我们要移除他在将他放置到头结点的位置

        if (node != null) {
            remove(node, false);
            setHead(node);
            return node.value;
        }

        //如果不存在
        return null;
    }


    public void remove(LRUNode node, boolean flag) {
        //需要考虑需要删除的节点是head或者是tail的情况
        //如果是head那么就只要让head=node.next就好了，如果是tail那么就只要让tail=node.pre就好了
        if (node.pre != null) {
            node.pre.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        } else {
            tail = node.pre;
        }
        node.pre = null;
        node.next = null;
        if (flag) {
            map.remove(node.key);
        }
    }

}
